package 剑指offer;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * 滑动窗口的最大值
 * https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/dong-hua-yan-shi-dan-diao-dui-lie-jian-z-unpy/
 */
public class Offer59_JZ64 {
    // 暴力法
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) {
            return new int[0];
        }
        int left = 0;
        int right = k-1;
        int[] maxArr = new int[nums.length-k+1];
        for (int i=0; i<maxArr.length; i++) {
            maxArr[i] = findMax(nums, left, right);
            left+=1;
            right+=1;
        }
        return maxArr;
    }

    public int findMax(int[] nums, int left, int right) {
        int max = Integer.MIN_VALUE;
        for (int i=left; i<=right; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
        }
        return max;
    }

    // 双端队列法
    public int[] maxSlidingWindow2(int[] nums, int k) {
        if (nums.length == 0 || k == 0) {
            return new int[0];
        }
        int[] maxArr = new int[nums.length-k+1];
        LinkedList<Integer> dequeue = new LinkedList<>();
        for (int right=0; right<nums.length; right++) {
            while (!dequeue.isEmpty() && nums[right]>nums[dequeue.peekLast()]) {
                dequeue.removeLast();
            }
            dequeue.addLast(right);
            int left = right-k+1;
            if (dequeue.peekFirst() < left) {
                dequeue.removeFirst();
            }
            if (right+1 >= k) {
                maxArr[left] = nums[dequeue.peekFirst()];
            }
        }
        return maxArr;
    }

    public static void main(String[] args) {
        int[] arr = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        Offer59_JZ64 demo = new Offer59_JZ64();
        System.out.println(Arrays.toString(demo.maxSlidingWindow2(arr, k)));
    }
}
